#include <iostream>
#include <string>
#include <vector>       //vector<bool>
#include <iterator>
#include <algorithm>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>      //strlen()
#include <climits>      //ULONG_MAX
#include <cmath>      //ULONG_MAX
using namespace std;
class BigInt {
	private:
		unsigned char *digits;
		unsigned long int length;
		unsigned long int digitCount;
		bool positive;
		static const double FACTOR;
		static unsigned long int int2uchar(     unsigned long int number, 
				unsigned char *digits, 
				unsigned long int padding);
		static void char2uchar( unsigned char *array, 
				unsigned long int length);
		static bool allCharsAreDigits(  const char *array, 
				unsigned long int length);
		static int compareNumbers(      unsigned char *a, unsigned long int na,
				unsigned char *b, unsigned long int nb, 
				bool aPositive = true, 
				bool bPositive = true);
		static void karatsubaMultiply(  unsigned char *a, unsigned char *b,
				unsigned long int n, 
				unsigned char *buffer);
		static void longMultiply(       unsigned char *a, unsigned long int na,
				unsigned char *b, unsigned long int nb,
				unsigned char *result);
		static unsigned char quickAdd(  unsigned char *a, unsigned char *b, 
				unsigned long int n);
		static void quickSub(   unsigned char *a, unsigned char *b, 
				unsigned char *end, unsigned long int n);
		static void divide(     const BigInt &dividend, const BigInt &divisor,
				BigInt &quotient, BigInt &remainder);
		static unsigned long int toInt(unsigned char *digits, int n);
		static bool add(unsigned char *shorter, unsigned long int nShorter, 
				unsigned char *longer, unsigned long int nLonger, 
				unsigned char *result, int nResult, 
				bool doFill = true);
		BigInt &shiftLeft(unsigned long int n);
		BigInt &shiftRight(unsigned long int n);
		void expandTo(unsigned long int n);
	public:
		BigInt();
		BigInt(const char *charNum);
		BigInt(unsigned long int intNum);
		BigInt(const std::string &str);
		BigInt(const BigInt &number);
		BigInt &operator =(const BigInt &rightNumber);
		~BigInt();
		operator std::string() const;
		friend std::ostream &operator <<(       std::ostream &cout, 
				const BigInt &number);
		friend std::istream &operator >>(       std::istream &cin, 
				BigInt &number);
		friend bool operator <(const BigInt &a, const BigInt &b);
		friend bool operator <=(const BigInt &a, const BigInt &b);
		friend bool operator >(const BigInt &a, const BigInt &b);
		friend bool operator >=(const BigInt &a, const BigInt &b);
		friend bool operator ==(const BigInt &a, const BigInt &b);
		friend bool operator !=(const BigInt &a, const BigInt &b);
		friend BigInt operator + (const BigInt &a, const BigInt &b);
		BigInt &operator+();
		BigInt &operator++();
		BigInt operator++(int);
		BigInt &operator+=(const BigInt &number);
		BigInt operator-() const;
		friend BigInt operator-(const BigInt &a, const BigInt &b);
		BigInt &operator--();
		BigInt operator--(int);
		BigInt &operator-=(const BigInt &number);
		friend BigInt operator*(const BigInt &a, const BigInt &b);
		BigInt &operator*=(const BigInt &number);
		friend BigInt operator/(const BigInt &a, const BigInt &b);
		BigInt &operator/=(const BigInt &number);
		friend BigInt operator%(const BigInt &a, const BigInt &b);
		BigInt &operator%=(const BigInt &number);
		BigInt GetPower(unsigned long int n) const;
		void SetPower(unsigned long int n);
		BigInt GetPower(BigInt n) const;
		void SetPower(BigInt n);
		BigInt GetPowerMod(const BigInt &b, const BigInt &n) const;
		void SetPowerMod(const BigInt &b, const BigInt &n);
		unsigned char GetDigit(unsigned long int index) const;
		void SetDigit(unsigned long int index, unsigned char value);
		unsigned long int Length() const;
		bool IsPositive() const;
		bool IsOdd() const;
		std::string ToString(bool forceSign = false) const;
		bool EqualsZero() const;
		BigInt Abs() const;
};

inline BigInt::~BigInt()
{
	delete[] digits;
}

inline BigInt &BigInt::operator+()
{
	return *this;
}

inline unsigned long int BigInt::Length() const
{
	return digitCount;
}

inline bool BigInt::IsPositive() const
{
	return positive;
}

inline bool BigInt::IsOdd() const
{
	return digits[0] & 1;
}

inline bool BigInt::EqualsZero() const
{
	return digitCount == 1 && digits[0] == 0;
}

static const BigInt BigIntZero;
static const BigInt BigIntOne(1L);
const double BigInt::FACTOR = 1.6;
static const BigInt ULongMax(ULONG_MAX);
static const BigInt SqrtULongMax
(static_cast<unsigned long int>(sqrt(static_cast<double>(ULONG_MAX))));

unsigned long int BigInt::int2uchar(unsigned long int number, 
		unsigned char *digits, 
		unsigned long int padding = 0L)
{
	int i(0);
	do
	{
		digits[i++] = (unsigned char) (number % 10);
		number /= 10;
	} while (number > 0L);

	std::fill_n(digits + i, padding, 0);
	return i;
}

void BigInt::char2uchar(unsigned char *array, 
		unsigned long int length)
{
	for (unsigned long int i(0L); i < length; i++)
		array[i] -= '0';
}

bool BigInt::allCharsAreDigits( const char *array, 
		unsigned long int length)
{
	for (unsigned long int i(0L); i < length; i++)
		if (array[i] < '0' || array[i] > '9')
			return false;

	return true;
}

int BigInt::compareNumbers(     unsigned char *a, unsigned long int na,      
		unsigned char *b, unsigned long int nb,
		bool aPositive, bool bPositive)
{
	if (na < nb || !aPositive && bPositive)
		return 2;
	else if (na > nb || aPositive && !bPositive)
		return 1;

	for (long int i = na - 1; i >= 0L; i--)
		if (a[i] != b[i])
		{
			if (a[i] < b[i])    // |a| < |b|
				if (aPositive)
					return 2;       // a < b
				else
					return 1;       // a > b
			else                                // |a| > |b|
				if (aPositive)  
					return 1;       // a > b
				else
					return 2;       // a < b
		}
	return 0;
}

void BigInt::karatsubaMultiply( unsigned char *a, unsigned char *b,
		unsigned long int n, unsigned char *buf1)
{
	if (compareNumbers(a, n, SqrtULongMax.digits, SqrtULongMax.digitCount) != 1
			&&
			compareNumbers(b, n, SqrtULongMax.digits, SqrtULongMax.digitCount) != 1
	   )
	{
		int2uchar(toInt(a, n) * toInt(b, n), buf1, n << 1);
		return;
	}

	unsigned long int       nh(n >> 1), nl(n - nh), nt(nl + 1);     
	unsigned char *t1(buf1 + (n << 1));

	BigInt::add(a + nl, nh, a, nl, buf1, nt);
	BigInt::add(b + nl, nh, b, nl, buf1 + nt, nt);
	BigInt::karatsubaMultiply(a + nl, b + nl, nh, t1);      //p1
	BigInt::karatsubaMultiply(a, b, nl, t1 + (nh << 1));            //p2
	BigInt::karatsubaMultiply(buf1, buf1 + nt, nt, t1 + (n << 1));//p3

	unsigned long int power(n);
	if (power & 1)
		power++;
	a = buf1 + (power >> 1);
	std::fill(buf1, a, 0);
	std::copy(t1 + (n << 1), t1 + ((n + nl) << 1) + 1, a);
	std::fill(a + (nl << 1) + 1, t1, 0);

	BigInt::quickSub(a, t1 + (nh << 1), t1, nl);

	BigInt::quickSub(a, t1, t1, nh);

	a = buf1 + power;
	BigInt::quickAdd(a, t1, nh);

	unsigned char carry = BigInt::quickAdd(buf1, t1 + (nh << 1), nl);
	a = buf1 + (nl << 1);
	for (unsigned long int i(0L); carry; i++)
	{
		a[i] += 1;
		carry = a[i] / 10;
		a[i] %= 10; 
	}
}

void BigInt::longMultiply(      unsigned char *a, unsigned long int na,
		unsigned char *b, unsigned long int nb,
		unsigned char *result)
{
	std::fill_n(result, na + nb, 0);
	unsigned char mult(0);
	int carry(0);

	for (unsigned long int i(0L); i < na; i++)
	{
		for (unsigned long int j(0L); j < nb; j++)
		{
			mult = a[i] * b[j] + result[i + j] + carry;
			result[i + j] = static_cast<int>(mult) % 10;
			carry = static_cast<int>(mult) / 10;
		}
		if (carry)
		{
			result[i + nb] += carry;
			carry = 0;
		}
	}
}

unsigned char BigInt::quickAdd( unsigned char *a, unsigned char *b, 
		unsigned long int n)
{
	unsigned char carry(0), sum(0);
	for (unsigned long int i(0L); i < (n << 1); i++)
	{
		sum = a[i] + b[i] + carry;
		carry = sum / 10;
		a[i] = sum % 10;
	}
	return carry;
}

void BigInt::quickSub(  unsigned char *a, unsigned char *b, 
		unsigned char *end, unsigned long int n)
{
	unsigned char carry(0), sum(0);
	for (unsigned long int i(0L); i < (n << 1); i++)
	{
		sum = 10 + a[i] - (b[i] + carry);
		if (sum < 10)   //carry
		{
			a[i] = sum;
			carry = 1;
		}
		else
		{
			a[i] = sum % 10;
			carry = 0;
		}
	}
	a = &a[n << 1];
	for (; carry && a < end; a++)
		if (*a)
		{
			(*a)--;
			break;
		}
		else
			*a = 9;
}

void BigInt::divide(const BigInt &dividend, const BigInt &divisor, 
		BigInt &quotient, BigInt &remainder)
{
	BigInt Z1, R, X(dividend.Abs());
	quotient = BigIntZero;
	remainder = BigIntZero;

	while (BigInt::compareNumbers(  X.digits, X.digitCount, 
				divisor.digits, divisor.digitCount, 
				true, true) != 2)       
	{
		unsigned long int O(X.digitCount - divisor.digitCount);
		if (O <= ULongMax.digitCount - 2)
		{
			unsigned long int i;
			if (X.digitCount > ULongMax.digitCount - 1)
				i = ULongMax.digitCount - 1;
			else
				i = X.digitCount;
			unsigned long int j(i - O);
			Z1 =    toInt(X.digits + X.digitCount - i, i) / 
				toInt(divisor.digits + divisor.digitCount - j, j);
		}
		else
		{
			unsigned long int i(ULongMax.digitCount - 1);
			unsigned long int j;
			if (divisor.digitCount > ULongMax.digitCount - 2)
				j = ULongMax.digitCount - 2;
			else
				j = divisor.digitCount;
			Z1 =    toInt(X.digits + X.digitCount - i, i) / 
				toInt(divisor.digits + divisor.digitCount - j, j);
			Z1.shiftLeft(O - Z1.digitCount);                
		}

predictZ1:
		R = (Z1 * divisor).Abs();

		if (X >= R)
		{
			X = X - R;
			quotient += Z1;
		}
		else
		{
			if (Z1.digitCount > 1)
				Z1.shiftRight(1);
			else
				--Z1;
			goto predictZ1;
		}
	}

	remainder = X;
}

unsigned long int BigInt::toInt(unsigned char *digits, int n)
{
	unsigned long int newInt(0L);
	unsigned long int powerOf10(1);
	for (int i(0); i < n; i++)
	{
		newInt += digits[i] * powerOf10;
		powerOf10 *= 10;
	}
	return newInt;
}

bool BigInt::add(unsigned char *shorter, unsigned long int nShorter,
		unsigned char *longer, unsigned long int nLonger, 
		unsigned char *result, int nResult, bool doFill)
{
	unsigned char subSum(0);
	unsigned char subCarry(0);

	unsigned long int i(0L);

	for (; i < nShorter; i++)
	{
		subSum = longer[i] + shorter[i] + subCarry;
		subCarry = subSum / 10;
		result[i] = subSum % 10;
	}

	for (; i < nLonger; i++)
	{
		subSum = longer[i] + subCarry;
		subCarry = subSum / 10;
		result[i] = subSum % 10;
	}

	if (doFill)
		std::fill_n(result + i, nResult - i, 0);

	if (subCarry)
	{
		result[i++] = 1;
		return true;
	}
	return false;
}

BigInt &BigInt::shiftLeft(unsigned long int n)
{
	if (EqualsZero())
		return *this;
	if (length <= digitCount + n + 2)
		expandTo(digitCount + n + 2);

	std::copy_backward(digits, digits + digitCount, digits + n + digitCount);
	std::fill_n(digits, n, 0);
	digitCount += n;
	return *this;
}

BigInt &BigInt::shiftRight(unsigned long int n)
{
	if (n >= digitCount)
		throw "Error BIGINT00: Overflow on shift right.";

	std::copy_backward(     digits + n, digits + digitCount, 
			digits + digitCount - n);
	digitCount -= n;
	return *this;
}

void BigInt::expandTo(unsigned long int n)
{
	unsigned long int oldLength(length);
	length = n;
	unsigned char *oldDigits(digits);
	try
	{
		digits = new unsigned char[length];
	}
	catch (...)
	{
		delete[] digits;
		digits = oldDigits;
		length = oldLength;
		throw "Error BIGINT01: BigInt creation error (out of memory?).";
	}

	std::copy(oldDigits, oldDigits + digitCount, digits);
	delete[] oldDigits;
}

BigInt::BigInt() : digits(0), length(10), digitCount(1), positive(true)
{
	try
	{
		digits = new unsigned char[length];
	}
	catch (...)
	{
		delete[] digits;
		throw "Error BIGINT02: BigInt creation error (out of memory?).";
	}

	digits[0] = 0;
}

BigInt::BigInt(const char * charNum) : digits(0)
{
	digitCount = (unsigned long int) strlen(charNum);

	if (digitCount == 0L)
		throw "Error BIGINT03: Input string empty.";
	else 
	{
		switch (charNum[0])
		{
			case '+':
				digitCount--;
				charNum++;
				positive = true;
				break;
			case '-':
				digitCount--;
				charNum++;
				positive = false;
				break;
			default:
				positive = true;
		}
	}

	while (charNum[0] == '0')
	{
		charNum++;
		digitCount --;
	}

	if (! BigInt::allCharsAreDigits(charNum, digitCount))
		throw "Error BIGINT04: Input string contains characters"
			" other than digits.";

	if (charNum[0] == '\0')
	{
		digitCount = 1;
		charNum--;
		positive = true;
	}

	length = (unsigned long int)(digitCount * BigInt::FACTOR + 1);

	try
	{
		digits = new unsigned char[length];
	}
	catch (...)
	{
		delete[] digits;
		throw "Error BIGINT05: BigInt creation error (out of memory?).";
	}

	std::reverse_copy(charNum, charNum + digitCount, digits);
	BigInt::char2uchar(digits, digitCount);
}

BigInt::BigInt(unsigned long int intNum) : digits(0)
{
	positive = true;
	unsigned char tempDigits[40] = {0};
	digitCount = int2uchar(intNum, tempDigits);
	length = (unsigned long int)(digitCount * BigInt::FACTOR + 1);
	try
	{
		digits = new unsigned char[length];
	}
	catch (...)
	{
		delete [] digits;
		throw "Error BIGINT06: BigInt creation error (out of memory?).";
	}

	std::copy(tempDigits, tempDigits + digitCount, digits);
}

BigInt::BigInt(const std::string &str) :        digits(0), length(10), 
	digitCount(1), positive(true)
{
	try
	{
		digits = new unsigned char[length];
	}
	catch (...)
	{
		delete[] digits;
		throw "Error BIGINT07: BigInt creation error (out of memory?).";
	}

	//initialize to 0
	digits[0] = 0;
	BigInt a(str.c_str());
	*this = a;
}

BigInt::BigInt(const BigInt &rightNumber) : length(rightNumber.length),
	digitCount(rightNumber.digitCount), positive(rightNumber.positive)
{
	if (length <= digitCount + 2 || length > (digitCount << 2))
		length = (unsigned long int) (digitCount * BigInt::FACTOR + 1);
	try
	{
		digits = new unsigned char[length];
	}
	catch (...)
	{
		delete[] digits;
		throw "Error BIGINT08: BigInt creation error (out of memory?).";
	}

	std::copy(rightNumber.digits, rightNumber.digits + digitCount, digits);
}

BigInt::operator std::string() const
{
	return ToString();
}

BigInt &BigInt::operator =(const BigInt &rightNumber)
{
	if (length < rightNumber.digitCount + 2 || 
			length > (rightNumber.digitCount << 2)) 
	{
		length = (unsigned long int) 
			(rightNumber.digitCount * BigInt::FACTOR + 1);
		unsigned char *tempDigits(digits);

		try
		{
			digits = new unsigned char[length];
		}
		catch (...)
		{
			delete[] digits;
			digits = tempDigits;
			throw "Error BIGINT09: BigInt assignment error (out of memory?).";
		}
		delete[] tempDigits;
	}
	else if (this == &rightNumber)
		return *this;

	digitCount = rightNumber.digitCount;
	positive = rightNumber.positive;
	std::copy(rightNumber.digits, rightNumber.digits + digitCount, digits);
	return *this;
}

std::ostream &operator <<(std::ostream &cout, const BigInt &number)
{
	if (!number.positive)
		cout << '-';
	for (int i = number.digitCount - 1; i >= 0; i--)
		cout << (int(number.digits[i]));

	return cout;
}

std::istream &operator >>(std::istream &cin, BigInt &number)
{
	std::string newNumber;
	std::cin >> std::ws >> newNumber;
	if (!cin)
	{
		cin.clear();
		throw "Error BIGINT16: Input stream error.";
	}

	number = newNumber;
	return cin;
}

bool operator <(const BigInt &a, const BigInt &b)
{
	if (BigInt::compareNumbers(     a.digits, a.digitCount,
				b.digits, b.digitCount, 
				a.positive, b.positive) == 2)
		return true;
	return false;
}

bool operator <=(const BigInt &a, const BigInt &b)
{
	if (BigInt::compareNumbers(     a.digits, a.digitCount,
				b.digits, b.digitCount, 
				a.positive, b.positive) == 1)
		return false;
	return true;
}

bool operator >(const BigInt &a, const BigInt &b)
{
	if (BigInt::compareNumbers(     a.digits, a.digitCount,
				b.digits, b.digitCount, 
				a.positive, b.positive) == 1)
		return true;
	return false;
}

bool operator >=(const BigInt &a, const BigInt &b)
{
	if (BigInt::compareNumbers(     a.digits, a.digitCount,
				b.digits, b.digitCount, 
				a.positive, b.positive) == 2)
		return false;
	return true;
}

bool operator ==(const BigInt &a, const BigInt &b)
{
	if (BigInt::compareNumbers(     a.digits, a.digitCount,
				b.digits, b.digitCount, 
				a.positive, b.positive))
		return false;
	return true;
}

bool operator !=(const BigInt &a, const BigInt &b)
{
	if (BigInt::compareNumbers(     a.digits, a.digitCount,
				b.digits, b.digitCount, 
				a.positive, b.positive))
		return true;
	return false;
}

BigInt operator +(const BigInt &a, const BigInt &b)
{
	if (a.positive && !b.positive)
		return a - (-b);
	else if (!a.positive && b.positive)
		return b - (-a);

	const BigInt *shorter, *longer;
	if (BigInt::compareNumbers(     a.digits, a.digitCount, 
				b.digits, b.digitCount) == 1)
	{
		shorter = &b;
		longer = &a;
	}
	else
	{
		shorter = &a;
		longer = &b;
	}

	BigInt sum(*longer);

	bool overflow = BigInt::add(shorter->digits, shorter->digitCount, 
			longer->digits, longer->digitCount, 
			sum.digits, 0, false);
	if (overflow)
		sum.digitCount++;

	return sum;
}

BigInt &BigInt::operator++()
{
	return *this += BigIntOne;
}

BigInt BigInt::operator++(int)
{
	BigInt temp(*this);
	*this += BigIntOne;
	return temp;
}

BigInt &BigInt::operator+=(const BigInt &number)
{
	*this = *this + number;
	return *this;
}

BigInt BigInt::operator-() const
{
	if (!this->EqualsZero())
	{
		BigInt temp(*this);
		temp.positive = !temp.positive;
		return temp;
	}
	return *this;
}

BigInt operator-(const BigInt &a, const BigInt &b)
{
	if (!a.positive && b.positive)
	{
		return -((-a) + b);
	} 
	if (a.positive && !b.positive)
	{
		return a + (-b);
	}

	const int cmpAbs = BigInt::compareNumbers(  a.digits, a.digitCount, 
			b.digits, b.digitCount); 
	if ((cmpAbs == 0) && (a.positive == b.positive))
	{
		return BigIntZero;
	}

	const BigInt *shorter, *longer;
	bool sign(a.positive);  //the sign of the result
	if (cmpAbs != 2)        // a >= b
	{
		shorter = &b;
		longer = &a;
	}
	else
	{
		shorter = &a;
		longer = &b;
		sign = !sign;
	}

	BigInt result(*longer);
	result.positive = sign;
	const BigInt shorterCopy(*shorter);
	const int rDigits(shorterCopy.digitCount);
	bool overflow(false);

	for (int i(0); i < rDigits; i++)
	{
		overflow = (longer->digits[i] - shorterCopy.digits[i]) < 0;
		if (overflow)
		{
			result.digits[i] = longer->digits[i] + 10 - shorterCopy.digits[i];
			shorterCopy.digits[i+1]++;
		}
		else
			result.digits[i] = longer->digits[i] - shorterCopy.digits[i];
	}

	if (overflow && result.digits[rDigits] == 0)
	{
		result.digits[rDigits] = 9;

		int i(rDigits + 1);
		for (; result.digits[i] == 0; i++)
			result.digits[i] = 9;

		result.digits[i] -= 1;
	}   //there is a carry but there will be no more carries
	else if (overflow)
		result.digits[rDigits]--;

	for (int i(result.digitCount - 1); i > 0; i--)
		if (result.digits[i] == 0)
			result.digitCount--;
		else
			break;

	return result;
}

BigInt &BigInt::operator--()
{
	*this = *this - BigIntOne;
	return *this;
}

BigInt BigInt::operator--(int)
{
	BigInt temp(*this);
	*this = *this - BigIntOne;
	return temp;
}

BigInt &BigInt::operator-=(const BigInt &number)
{
	*this = *this - number;
	return *this;   
}

BigInt operator*(const BigInt &a, const BigInt &b)
{
	if (a.EqualsZero() || b.EqualsZero())
		return BigIntZero;

	//this controls wether Karatsuba algorithm will be used for multiplication
#ifdef KARATSUBA         
	int n((a.digitCount < b.digitCount ? b.digitCount : a.digitCount));

	unsigned char *buffer(0);

	try
	{
		buffer = new unsigned char[11 * n];
	}
	catch (...)
	{
		delete[] buffer;
		throw "Error BIGINT10: Not enough memory?";
	}

	unsigned char *bb(buffer + n), *bc(bb + n);

	std::copy(a.digits, a.digits + a.digitCount, buffer);
	std::fill(buffer + a.digitCount, buffer + n, 0);        
	std::copy(b.digits, b.digits + b.digitCount, bb);
	std::fill(bb + b.digitCount, bb + n, 0);

	BigInt::karatsubaMultiply(buffer, bb, n, bc);

	n <<= 1;
#else  
	int n = a.digitCount + b.digitCount;

	unsigned char *buffer = new unsigned char[n];

	BigInt::longMultiply(   a.digits, a.digitCount, 
			b.digits, b.digitCount, buffer);

	unsigned char *bc(buffer);
#endif /*KARATSUBA*/

	BigInt bigIntResult;    //we assume it's a positive number
	if (a.positive != b.positive)
		bigIntResult.positive = false;
	bigIntResult.expandTo(n + 10);
	std::copy(bc, bc + n, bigIntResult.digits);
	for (unsigned long int i = n - 1; i > 0L; i--)
	{
		if (bigIntResult.digits[i])
		{
			bigIntResult.digitCount = i + 1;
			break;
		}
	}
	delete[] buffer;

	return bigIntResult;
}

BigInt &BigInt::operator*=(const BigInt &number)
{
	*this = *this * number;
	return *this;
}

BigInt operator /(const BigInt &a, const BigInt &b)
{
	if (b.EqualsZero())
		throw "Error BIGINT11: Attempt to divide by zero.";

	int comparison(BigInt::compareNumbers(  a.digits, a.digitCount, 
				b.digits, b.digitCount));

	if (a.EqualsZero() || comparison == 2)
		return BigIntZero;

	if (comparison == 0)
		if (a.positive == b.positive)
			return BigIntOne;
		else 
			return -BigIntOne;

	BigInt quotient, remainder;
	BigInt::divide(a, b, quotient, remainder);
	if (a.positive != b.positive)
		quotient.positive = false;
	return quotient;
}

BigInt &BigInt::operator /=(const BigInt &number)
{
	*this = *this / number;
	return *this;
}

BigInt operator%(const BigInt &a, const BigInt &b)
{
	if (b.EqualsZero())
		throw "Error BIGINT12: Attempt to divide by zero.";

	int comparison(BigInt::compareNumbers(  a.digits, a.digitCount, 
				b.digits, b.digitCount));

	if (comparison == 0)
		return BigIntZero;

	if (comparison == 2 && a.positive)
		return a;

	BigInt quotient, remainder;
	BigInt::divide(a, b, quotient, remainder);
	if (!a.positive && !remainder.EqualsZero())
		remainder.positive = false;
	return remainder;
}

BigInt &BigInt::operator%=(const BigInt &number)
{
	*this = *this % number;
	return *this;
}

BigInt BigInt::GetPower(unsigned long int n) const
{
	BigInt result(BigIntOne);
	BigInt base(*this);

	while (n)
	{
		if (n & 1)
		{
			result = result * base;
			n--;
		}
		n /= 2;
		base = base * base;
	}

	if (!positive && (n & 1))
		result.positive = false;
	return result;
}

void BigInt::SetPower(unsigned long int n)
{
	*this = (*this).GetPower(n);
}

BigInt BigInt::GetPower(BigInt n) const
{
	if (!n.positive)
		throw "Error BIGINT13: Negative exponents not supported!";

	BigInt result(BigIntOne);
	BigInt base(*this);
	BigInt bigIntTwo(BigIntOne + BigIntOne);

	while (!n.EqualsZero())
	{
		if (n.digits[0] & 1)
		{
			result = result * base;
			n--;
		}
		n = n / bigIntTwo;
		base = base * base;
	}

	if (!positive && (n.digits[0] & 1))
		result.positive = false;
	return result;
}

void BigInt::SetPower(BigInt n)
{
	*this = (*this).GetPower(n);
}

BigInt BigInt::GetPowerMod(const BigInt &b, const BigInt &n) const
{
	BigInt a(*this);
	a.SetPowerMod(b, n);
	return a;
}

void BigInt::SetPowerMod(const BigInt &b, const BigInt &n)
{
	if (!b.positive)
		throw "Error BIGINT14: Negative exponent not supported.";
	const BigInt a(*this);
	BigInt bCopy(b), q, r;
	const BigInt two(BigIntOne + BigIntOne);

	std::vector<bool> bits;
	while (!bCopy.EqualsZero())
	{
		BigInt::divide(bCopy, two, q, r);
		bCopy = q;
		if (r.EqualsZero())
			bits.push_back(false);
		else
			bits.push_back(true);
	}

	*this = BigIntOne;
	for (int i = (int) bits.size() - 1; i >= 0; i--)
	{
		BigInt::divide(*this * *this, n, q, *this);
		if (bits[i])
			BigInt::divide(*this * a, n, q, *this);
	}
}

unsigned char BigInt::GetDigit(unsigned long int index) const
{
	if (index >= digitCount)
		throw "Error BIGINT15: Index out of range.";

	return digits[index];
}

void BigInt::SetDigit(unsigned long int index, unsigned char value)
{
	if (index >= digitCount)
		throw "Error BIGINT15: Index out of range.";
	if (value > 9)
		throw "Error BIGINT16: Digit value out of range.";

	digits[index] = value;
}

std::string BigInt::ToString(bool forceSign) const
{
	std::string number;
	if (!positive)
		number.push_back('-');
	for (int i = digitCount - 1; i >= 0; i--)
		number.push_back(char(digits[i]) + '0');

	return number;
}

BigInt BigInt::Abs() const
{
	return ((positive) ? *this : -(*this)); 
}


/* main
 *  * */
int main() {
	const unsigned long limit = 215;
	unsigned long t;
	unsigned long n;
	BigInt N;
	cin >> t;
	cin >> n;
	do {
		// Original Area + lines + points made from lines 
		// 1 + C(n,2) + C(n,4)
		//cout << N*(N-1)/2 + N*(N-1)*(N-2)*(N-3)/24 +1 << endl;
		unsigned long nM1 = n-1;
		unsigned long nM2 = n-2;
		unsigned long nM3 = n-3;
		if (n <= limit) {
			cout << n*nM1/2 + n*nM1*nM2*nM3/24 + 1 << endl;
		} else {
			N = 1;
			if( (n & 0x01UL) != 0) { 
				nM1 >>=  1; 
				nM3 >>=  1; 
				N += (BigInt(n) * nM1); 
				(nM1 & 0x01UL) == 0 ? nM1 >>= 1 : nM3 >>= 1; 
			} else {
				n >>= 1; 
				nM2 >>= 1; 
				N += (BigInt(n) * nM1);
				(n & 0x01UL) == 0 ? n >>= 1 : nM2 >>= 1; 
			}

			// devide by 3	
			if(		 n   % 3 == 0) n   /= 3;
			else if (nM1 % 3 == 0) nM1 /= 3;
			else if (nM2 % 3 == 0) nM2 /= 3;
			else if (nM3 % 3 == 0) nM3 /= 3;
			else cout << "This is killing Maths!" << endl;

			N += (BigInt(n) * BigInt(nM1) * BigInt(nM2) * nM3);
			cout << N << endl;
		}
		cin >> n;
	} while(cin.eof() == false && --t > 0);
	return 0;
}
